<!DOCTYPE html>
<html lang="zh-CN">
  <head>
  <meta charset="UTF-8">
  <meta 
    name="viewport"
    content="width=device-width, initial-scale=1.0, minimum-scale=1.0">
  <meta 
    http-equiv="X-UA-Compatible" 
    content="ie=edge">
  <meta 
    name="theme-color" 
    content="#fff" 
    id="theme-color">
  <meta 
    name="description" 
    content="霜序廿的个人网站">
  <link 
    rel="icon" 
    href="https://api2.mubu.com/v3/photo/654b368e-b847-4122-982c-86d90b3f5275.jpg">
  <title>哈夫曼树</title>
  
    
      <meta 
        property="og:title" 
        content="哈夫曼树">
    
    
      <meta 
        property="og:url" 
        content="https://shuangxunian.github.io/2021/06/13/huffman/index.html">
    
    
      <meta 
        property="og:img" 
        content="https://api2.mubu.com/v3/photo/654b368e-b847-4122-982c-86d90b3f5275.jpg">
    
    
      <meta 
        property="og:img" 
        content="一篇关于哈夫曼树的详细文章">
    
    
      <meta 
        property="og:type" 
        content="article">
      <meta 
        property="og:article:published_time" 
        content="2021-06-13">
      <meta 
        property="og:article:modified_time" 
        content="2020-09-25">
      <meta 
        property="og:article:author" 
        content="霜序廿">
      
        
          <meta 
            property="og:article:tag" 
            content="树">
        
      
    
  
  <script>
    function loadScript(url, cb) {
      var script = document.createElement('script');
      script.src = url;
      if (cb) script.onload = cb;
      script.async = true;
      document.body.appendChild(script);
    }
    function loadCSS(href, data, attr) {
      var sheet = document.createElement('link');
      sheet.ref = 'stylesheet';
      sheet.href = href;
      sheet.dataset[data] = attr;
      document.head.appendChild(sheet);
    }
    function changeCSS(cssFile, data, attr) {
      var oldlink = document.querySelector(data);
      var newlink = document.createElement("link");
      newlink.setAttribute("rel", "stylesheet");
      newlink.setAttribute("href", cssFile);
      newlink.dataset.prism = attr;
      document.head.replaceChild(newlink, oldlink);
    }
  </script>
  
    
      
      
      
      
        
        
        
        <script>
          function prismThemeChange() {
            if(document.getElementById('theme-color').dataset.mode === 'dark') {
              if(document.querySelector('[data-prism]')) {
                changeCSS('/js/lib/prism/prism-tomorrow.min.css', '[data-prism]', 'prism-tomorrow');
              } else {
                loadCSS('/js/lib/prism/prism-tomorrow.min.css', 'prism', 'prism-tomorrow');
              }
            } else {
              if(document.querySelector('[data-prism]')) {
                changeCSS('/js/lib/prism/prism.min.css', '[data-prism]', 'prism');
              } else {
                loadCSS('/js/lib/prism/prism.min.css', 'prism', 'prism');
              }
            }
          }
          prismThemeChange()
        </script>
      
      
        
        <link rel="stylesheet" href="/js/lib/prism/prism-line-numbers.min.css">
      
    
  
  <script>
    // control reverse button
    var reverseDarkList = {
      dark: 'light',
      light: 'dark'
    };
    var themeColor = {
      dark: '#1c1c1e',
      light: '#fff'
    }
    // get the data of css prefers-color-scheme
    var getCssMediaQuery = function() {
      return window.matchMedia('(prefers-color-scheme: dark)').matches ? 'dark' : 'light';
    };
    // reverse current darkmode setting function
    var reverseDarkModeSetting = function() {
      var setting = localStorage.getItem('user-color-scheme');
      if(reverseDarkList[setting]) {
        setting = reverseDarkList[setting];
      } else if(setting === null) {
        setting = reverseDarkList[getCssMediaQuery()];
      } else {
        return;
      }
      localStorage.setItem('user-color-scheme', setting);
      return setting;
    };
    // apply current darkmode setting
  </script>
  
    <script>
      var setDarkmode = function(mode) {
      var setting = mode || localStorage.getItem('user-color-scheme');
      if(setting === getCssMediaQuery()) {
        document.documentElement.removeAttribute('data-user-color-scheme');
        localStorage.removeItem('user-color-scheme');
        document.getElementById('theme-color').content = themeColor[setting];
        document.getElementById('theme-color').dataset.mode = setting;
        prismThemeChange();
      } else if(reverseDarkList[setting]) {
        document.documentElement.setAttribute('data-user-color-scheme', setting);
        document.getElementById('theme-color').content = themeColor[setting];
        document.getElementById('theme-color').dataset.mode = setting;
        prismThemeChange();
      } else {
        document.documentElement.removeAttribute('data-user-color-scheme');
        localStorage.removeItem('user-color-scheme');
        document.getElementById('theme-color').content = themeColor[getCssMediaQuery()];
        document.getElementById('theme-color').dataset.mode = getCssMediaQuery();
        prismThemeChange();
      }
    };
    setDarkmode();
    </script>
  
  
  <link rel="preload" href="//at.alicdn.com/t/font_1946621_i1kgafibvw.css" as="style" >
  <link rel="preload" href="//at.alicdn.com/t/font_1952792_89b4ac4k4up.css" as="style" >
  
  
    <link rel="preload" href="/js/lib/lightbox/baguetteBox.min.js" as="script">
    <link rel="preload" href="/js/lib/lightbox/baguetteBox.min.css" as="style" >
  
  
    <link rel="preload" href="/js/lib/lozad.min.js" as="script">
  
  
  
  
  
  
  
  <link rel="stylesheet" href="/css/main.css">
  
  <link rel="stylesheet" href="//at.alicdn.com/t/font_1946621_i1kgafibvw.css">
  
  <link rel="stylesheet" href="//at.alicdn.com/t/font_1952792_89b4ac4k4up.css">
  
    <link rel="stylesheet" href="/js/lib/lightbox/baguetteBox.min.css">
  
<meta name="generator" content="Hexo 5.4.0"></head>

  <body>
    <div class="wrapper">
       
      <nav class="navbar">
  <div class="navbar-logo">
    <span class="navbar-logo-main">
      
        <img 
          class="navbar-logo-img" 
          src="https://api2.mubu.com/v3/photo/654b368e-b847-4122-982c-86d90b3f5275.jpg" 
          alt="blog logo">
      
      <span class="navbar-logo-dsc">霜序廿的个人网站</span>
    </span>
  </div>
  <div class="navbar-menu">
    
      <a 
        href="/" 
        class="navbar-menu-item">
        
          首页
        
      </a>
    
      <a 
        href="/archives" 
        class="navbar-menu-item">
        
          归档
        
      </a>
    
      <a 
        href="/tags" 
        class="navbar-menu-item">
        
          标签
        
      </a>
    
      <a 
        href="/categories" 
        class="navbar-menu-item">
        
          分类
        
      </a>
    
      <a 
        href="/about" 
        class="navbar-menu-item">
        
          关于
        
      </a>
    
      <a 
        href="/links" 
        class="navbar-menu-item">
        
          友链
        
      </a>
    
    <a 
      class="navbar-menu-item darknavbar" 
      id="dark">
      <i class="iconfont icon-weather"></i>
    </a>
    <a 
      class="navbar-menu-item searchnavbar" 
      id="search">
      <i 
        class="iconfont icon-search" 
        style="font-size: 1.2rem; font-weight: 400;">
      </i>
    </a>
  </div>
</nav> 
      
      <div 
        id="local-search" 
        style="display: none">
        <input
          class="navbar-menu-item"
          id="search-input"
          placeholder="请输入搜索内容..." />
        <div id="search-content"></div>
      </div>
      
      <div class="section-wrap">
        <div class="container">
          <div class="columns">
            <main class="main-column">
<article class="card card-content">
  <header>
    <h1 class="post-title">
      哈夫曼树
    </h1>
  </header>
  <div class="post-meta post-show-meta">
    <time datetime="2021-06-13T13:48:56.147Z">
      <i 
        class="iconfont icon-calendar" 
        style="margin-right: 2px;">
      </i>
      <span>2021-06-13</span>
    </time>
    
      <span class="dot"></span>
      
        <a 
          href="/categories/%E7%AE%97%E6%B3%95/" 
          class="post-meta-link">
          算法
        </a>
      
    
    
      <span class="dot"></span>
      <span>3.4k 字</span>
    
  </div>
  
    <div 
      class="post-meta post-show-meta" 
      style="margin-top: -10px;">
      <div style="display: flex; align-items: center;">
        <i 
          class="iconfont icon-biaoqian" 
          style="margin-right: 2px; font-size: 1.15rem;">
        </i>
        
          
          <a 
            href="/tags/%E6%A0%91/" 
            class="post-meta-link">
            树
          </a>
        
      </div>
    </div>
  
  </header>
  <div 
    id="section" 
    class="post-content">
    <h2 id="引入"><a href="#引入" class="headerlink" title="引入"></a>引入</h2><p>在学习编程的过程中，一定遇到过类似以下的情景：记录一个班的同学的成绩，通过分数输出评价。</p>
<pre class="line-numbers language-c" data-language="c"><code class="language-c"><span class="token keyword">if</span> <span class="token punctuation">(</span>score <span class="token operator">&lt;</span> <span class="token number">60</span><span class="token punctuation">)</span> <span class="token punctuation">&#123;</span>
    result <span class="token operator">=</span> <span class="token string">"不及格"</span><span class="token punctuation">;</span>
<span class="token punctuation">&#125;</span> <span class="token keyword">else</span> <span class="token keyword">if</span> <span class="token punctuation">(</span>score <span class="token operator">&lt;</span> <span class="token number">70</span><span class="token punctuation">)</span> <span class="token punctuation">&#123;</span>
    result <span class="token operator">=</span> <span class="token string">"及格"</span><span class="token punctuation">;</span>
<span class="token punctuation">&#125;</span> <span class="token keyword">else</span> <span class="token keyword">if</span> <span class="token punctuation">(</span>score <span class="token operator">&lt;</span> <span class="token number">80</span><span class="token punctuation">)</span> <span class="token punctuation">&#123;</span>
    result <span class="token operator">=</span> <span class="token string">"中等"</span><span class="token punctuation">;</span>
<span class="token punctuation">&#125;</span> <span class="token keyword">else</span> <span class="token keyword">if</span> <span class="token punctuation">(</span>score <span class="token operator">&lt;</span> <span class="token number">90</span><span class="token punctuation">)</span> <span class="token punctuation">&#123;</span>
    result <span class="token operator">=</span> <span class="token string">"良好"</span><span class="token punctuation">;</span>
<span class="token punctuation">&#125;</span> <span class="token keyword">else</span> <span class="token punctuation">&#123;</span>
    result <span class="token operator">=</span> <span class="token string">"优秀"</span><span class="token punctuation">;</span>
<span class="token punctuation">&#125;</span><span aria-hidden="true" class="line-numbers-rows"><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span></span></code></pre>

<p>假如根据统计结果或往年数据，得出每个阶段的比例如下所示：</p>
<table>
<thead>
<tr>
<th>分数</th>
<th>比例</th>
</tr>
</thead>
<tbody><tr>
<td>0~59</td>
<td>5%</td>
</tr>
<tr>
<td>60~69</td>
<td>15%</td>
</tr>
<tr>
<td>70~79</td>
<td>40%</td>
</tr>
<tr>
<td>80~89</td>
<td>30%</td>
</tr>
<tr>
<td>90~100</td>
<td>10%</td>
</tr>
</tbody></table>
<p>可以看到 70+ 和 80+ 的人数占大多数。在这种情况下，对于以上代码，前两层 if 命中率低，产生大量的多余判断。一般情况下没有问题，但是如果数据量很大，并且每层的 if 判断比较耗时，那么就需要对判断的流程进行结构的优化。</p>
<p>我们将每个 if 判断视为一个结点，整个流程将变成一个二叉树结构：</p>
<p><img  srcset="data:image/svg+xml,%3Csvg%20xmlns='http://www.w3.org/2000/svg'%20viewBox='0%200%20300%20300'%3E%3C/svg%3E" data-src="https://api2.mubu.com/v3/document_image/556eb2ac-fffb-4464-9c0e-65557a73daaa-3807603.jpg" class="lozad post-image"src="https://api2.mubu.com/v3/document_image/556eb2ac-fffb-4464-9c0e-65557a73daaa-3807603.jpg"></p>
<p>介绍一下树的深度：从根开始定义起，根为第1层，根的子结点为第2层，以此类推。这里我们以路径的角度去分析结点的深度。每个结点到根节点中间存在的树枝（线段）数称为该结点的路径长度，树的路径⻓度就是从树根到每一个结点的路径长度之和。</p>
<p>图中个结点的路径长度如下：</p>
<table>
<thead>
<tr>
<th>分数</th>
<th>路径长度</th>
</tr>
</thead>
<tbody><tr>
<td>A</td>
<td>1</td>
</tr>
<tr>
<td>A’</td>
<td>1</td>
</tr>
<tr>
<td>B</td>
<td>2</td>
</tr>
<tr>
<td>B’</td>
<td>2</td>
</tr>
<tr>
<td>C</td>
<td>3</td>
</tr>
<tr>
<td>C’</td>
<td>3</td>
</tr>
<tr>
<td>D</td>
<td>4</td>
</tr>
<tr>
<td>E</td>
<td>4</td>
</tr>
</tbody></table>
<p>整个树的路径长度为：1 + 1 + 2 + 2 + 3 + 3 + 4 + 4 = 20。</p>
<p>在本例中路径长度即代表了 if 判断的次数。D 的路径长度为 4 代表需要 4 次 判断才能得到结果 D。</p>
<p>结合之前的统计数据，我们将每种可能的结果（即每个叶子节点）的路径长度，乘上其发生的概率（即权值），最后加到一起，就得到了树的带权路径长度，简称 WPL （Weighted Path Length of Tree）。</p>
<p>计算树的路径长度时包含了所有的节点的路径长度。（可以理解根节点的路径为0）</p>
<p>计算树的 WPL 时只计算叶子节点的带权长度。</p>
<table>
<thead>
<tr>
<th>结点</th>
<th>路径长度</th>
<th>权值</th>
</tr>
</thead>
<tbody><tr>
<td>A</td>
<td>1</td>
<td>5</td>
</tr>
<tr>
<td>B</td>
<td>2</td>
<td>15</td>
</tr>
<tr>
<td>C</td>
<td>3</td>
<td>40</td>
</tr>
<tr>
<td>D</td>
<td>4</td>
<td>30</td>
</tr>
<tr>
<td>E</td>
<td>5</td>
<td>10</td>
</tr>
</tbody></table>
<p>整个树的 WPL 为：1 x 5 + 2 x 15 + 3 x 40 + 4 x 30 + 4 x 10 = 315。</p>
<p>这个数表示了在上述概率下，每种结果的平均路径长度，即判断一次成绩时 if 执行的平均次数，为 3.15 次。直观上来讲 4 个 if 平均执行 3.15 次确实不小。 如果依照概率从大到小来进行判断，依次判断 D、C、B、E、A ，也可以容易猜出 WPL 必然会小于 3.15。</p>
<p>除此之外，我们可以通过构建哈夫曼树，来进行最短路径的求解，得到如下最短路径树：</p>
<p><img  srcset="data:image/svg+xml,%3Csvg%20xmlns='http://www.w3.org/2000/svg'%20viewBox='0%200%20300%20300'%3E%3C/svg%3E" data-src="https://api2.mubu.com/v3/document_image/6ab4f215-5a1e-49e9-a6b1-2183183cc3b3-3807603.jpg" class="lozad post-image"src="https://api2.mubu.com/v3/document_image/6ab4f215-5a1e-49e9-a6b1-2183183cc3b3-3807603.jpg"></p>
<table>
<thead>
<tr>
<th>结点</th>
<th>路径长度</th>
<th>权值</th>
</tr>
</thead>
<tbody><tr>
<td>A</td>
<td>4</td>
<td>5</td>
</tr>
<tr>
<td>B</td>
<td>3</td>
<td>15</td>
</tr>
<tr>
<td>C</td>
<td>1</td>
<td>40</td>
</tr>
<tr>
<td>D</td>
<td>2</td>
<td>30</td>
</tr>
<tr>
<td>E</td>
<td>4</td>
<td>10</td>
</tr>
</tbody></table>
<p>整个树的 WPL 为：4 x 5 + 3 x 15 + 1 x 40 + 2 x 30 + 4 x 10 = 205。</p>
<p>相比于之前的 315 ，可以理解为 if 的平均执行次数从 3.15 次降低为 2.05 次，有明显的降低。</p>
<p>那么如何构建哈夫曼树呢？下面将介绍什么是哈夫曼树以及哈夫曼编码的原理。</p>
<h2 id="介绍"><a href="#介绍" class="headerlink" title="介绍"></a>介绍</h2><p><strong>哈夫曼树：</strong>给定 n 个权值作为 n 个叶子结点，构造一棵二叉树，若该树的带权路径长度（WPL）达到最小，称这样的二叉树为最优二叉树，也称为哈夫曼树（Huffman Tree，或称霍夫曼树）。哈夫曼树是带权路径长度最短的树，权值较大的结点离根较近。</p>
<p><strong>哈夫曼编码：</strong>在计算机中，每个字符都是通过二进制进行编码。我们把使用相同长度编码的方式称为定长编码。比如一个字符串 “Hello world!’’ 需要 12 个字节即  96 个二进制位来存储。但实际中每个字符出现的概率并不相同，比如字母 a、e、i、o、u 出现的概率可能会高，字母 x、z 出现的概率可能很低。哈夫曼编码就是一种基于概率实现的一种变长编码方式。出现次数较多的字符其编码长度就相应地小，反之其编码长度就相应的长。</p>
<p>哈夫曼编码是压缩界的始祖，虽然如今有更优秀的压缩方式，但其思想依旧影响着现在。哈夫曼编码有着广泛的应用，例如在 jpeg文件中，就应用了哈夫曼编码来实现最后一步的压缩；在数字电视大力发展的今天，哈夫曼编码成为了视频信号的主要压缩方式。应当说，哈夫曼编码出现，结束了熵编码不能实现最短编码的历史,也使哈夫曼编码成为一种非常重要的无损编码。</p>
<h2 id="构建"><a href="#构建" class="headerlink" title="构建"></a>构建</h2><p>如图所示的场景，我们使用三个二进制来对英文字母进行编码。文字包含 n 个字符则需要发送 3n 个二进制数据。</p>
<p><img  srcset="data:image/svg+xml,%3Csvg%20xmlns='http://www.w3.org/2000/svg'%20viewBox='0%200%20300%20300'%3E%3C/svg%3E" data-src="https://api2.mubu.com/v3/document_image/218316ac-d643-4a6d-8df7-4e41b786c160-3807603.jpg" class="lozad post-image"src="https://api2.mubu.com/v3/document_image/218316ac-d643-4a6d-8df7-4e41b786c160-3807603.jpg"></p>
<p>假设通过统计概率得知，每个字母的出现概率如下所示：</p>
<table>
<thead>
<tr>
<th>字符</th>
<th>概率</th>
</tr>
</thead>
<tbody><tr>
<td>A</td>
<td>27%</td>
</tr>
<tr>
<td>B</td>
<td>8%</td>
</tr>
<tr>
<td>C</td>
<td>15%</td>
</tr>
<tr>
<td>D</td>
<td>15%</td>
</tr>
<tr>
<td>E</td>
<td>30%</td>
</tr>
<tr>
<td>F</td>
<td>5%</td>
</tr>
</tbody></table>
<p>则我们可以通过构建哈夫曼树来进行变长编码。</p>
<p>哈夫曼树的构建步骤：</p>
<ol>
<li>取出集合中权值最小的两个结点，构建一颗二叉树，并从集合中移除这两个结点。</li>
<li>二叉树的根结点将视为一个新的结点，加入到集合中，其权值为两个子结点的权值之和。</li>
<li>重复步骤 1，直到集合中无结点。</li>
</ol>
<p>其中规定：</p>
<ul>
<li>权值小的作为左子树，权值大的作为右子树。（相等时左右无影响）</li>
<li>编码时左子树为 0，右子树为 1。</li>
</ul>
<p>根据步骤开始构建哈夫曼树：</p>
<ol>
<li>取出权值最小的两个结点 B:8 和 F:5 构建二叉树。且权值小的作为左子树，大的作为右子树。</li>
</ol>
<p><img  srcset="data:image/svg+xml,%3Csvg%20xmlns='http://www.w3.org/2000/svg'%20viewBox='0%200%20300%20300'%3E%3C/svg%3E" data-src="https://api2.mubu.com/v3/document_image/a7d36998-3676-4a0b-95bc-3a8c433e25b3-3807603.jpg" class="lozad post-image"src="https://api2.mubu.com/v3/document_image/a7d36998-3676-4a0b-95bc-3a8c433e25b3-3807603.jpg"><br><img  srcset="data:image/svg+xml,%3Csvg%20xmlns='http://www.w3.org/2000/svg'%20viewBox='0%200%20300%20300'%3E%3C/svg%3E" data-src="https://api2.mubu.com/v3/document_image/beeb5349-ac3c-46f3-9b5f-c79c94211159-3807603.jpg" class="lozad post-image"src="https://api2.mubu.com/v3/document_image/beeb5349-ac3c-46f3-9b5f-c79c94211159-3807603.jpg"><br><img  srcset="data:image/svg+xml,%3Csvg%20xmlns='http://www.w3.org/2000/svg'%20viewBox='0%200%20300%20300'%3E%3C/svg%3E" data-src="https://api2.mubu.com/v3/document_image/2cfd32e6-89e7-4fa3-9a4d-b655bc03b842-3807603.jpg" class="lozad post-image"src="https://api2.mubu.com/v3/document_image/2cfd32e6-89e7-4fa3-9a4d-b655bc03b842-3807603.jpg"></p>
<p>此时集合中的结点情况如上所示，N1 为新加入的节点，其权值为。</p>
<ol start="2">
<li>从新的集合中取出最小的两个节点 N1:13 和 C:15 构建二叉树。</li>
</ol>
<p><img  srcset="data:image/svg+xml,%3Csvg%20xmlns='http://www.w3.org/2000/svg'%20viewBox='0%200%20300%20300'%3E%3C/svg%3E" data-src="https://api2.mubu.com/v3/document_image/068b1fcd-3758-4511-ae1b-1b64796c4707-3807603.jpg" class="lozad post-image"src="https://api2.mubu.com/v3/document_image/068b1fcd-3758-4511-ae1b-1b64796c4707-3807603.jpg"><br><img  srcset="data:image/svg+xml,%3Csvg%20xmlns='http://www.w3.org/2000/svg'%20viewBox='0%200%20300%20300'%3E%3C/svg%3E" data-src="https://api2.mubu.com/v3/document_image/b34a537e-ec85-480f-8d78-2e1d07eb0c4f-3807603.jpg" class="lozad post-image"src="https://api2.mubu.com/v3/document_image/b34a537e-ec85-480f-8d78-2e1d07eb0c4f-3807603.jpg"></p>
<ol start="3">
<li>从集合中取出最小的两个节点 A1:13 和 C:15 构建二叉树，因为 N2 比这两个节点都大，不参与该步骤的操作，所以 A 和 D 将构建新的子树。</li>
</ol>
<p><img  srcset="data:image/svg+xml,%3Csvg%20xmlns='http://www.w3.org/2000/svg'%20viewBox='0%200%20300%20300'%3E%3C/svg%3E" data-src="https://api2.mubu.com/v3/document_image/c2b71082-1314-4633-a2c5-5ddd34afa962-3807603.jpg" class="lozad post-image"src="https://api2.mubu.com/v3/document_image/c2b71082-1314-4633-a2c5-5ddd34afa962-3807603.jpg"><br><img  srcset="data:image/svg+xml,%3Csvg%20xmlns='http://www.w3.org/2000/svg'%20viewBox='0%200%20300%20300'%3E%3C/svg%3E" data-src="https://api2.mubu.com/v3/document_image/c144f404-4fba-42db-8755-e43c456b1e1d-3807603.jpg" class="lozad post-image"src="https://api2.mubu.com/v3/document_image/c144f404-4fba-42db-8755-e43c456b1e1d-3807603.jpg"></p>
<ol start="4">
<li>从集合中取出最小的两个节点 N2:28 和 E:30 构建二叉树。</li>
</ol>
<p><img  srcset="data:image/svg+xml,%3Csvg%20xmlns='http://www.w3.org/2000/svg'%20viewBox='0%200%20300%20300'%3E%3C/svg%3E" data-src="https://api2.mubu.com/v3/document_image/46793d81-cd35-47e6-bb1c-fa8b3722fa51-3807603.jpg" class="lozad post-image"src="https://api2.mubu.com/v3/document_image/46793d81-cd35-47e6-bb1c-fa8b3722fa51-3807603.jpg"><br><img  srcset="data:image/svg+xml,%3Csvg%20xmlns='http://www.w3.org/2000/svg'%20viewBox='0%200%20300%20300'%3E%3C/svg%3E" data-src="https://api2.mubu.com/v3/document_image/419ac3f1-5479-4ae0-81ca-1cd6ba4b54fb-3807603.jpg" class="lozad post-image"src="https://api2.mubu.com/v3/document_image/419ac3f1-5479-4ae0-81ca-1cd6ba4b54fb-3807603.jpg"></p>
<ol start="5">
<li>从集合中剩余的两个节点N3:42 和 N4: 58 完成哈夫曼树的构建。</li>
</ol>
<p><img  srcset="data:image/svg+xml,%3Csvg%20xmlns='http://www.w3.org/2000/svg'%20viewBox='0%200%20300%20300'%3E%3C/svg%3E" data-src="https://api2.mubu.com/v3/document_image/d94c1f75-856e-47c0-ba07-656616a3fc9e-3807603.jpg" class="lozad post-image"src="https://api2.mubu.com/v3/document_image/d94c1f75-856e-47c0-ba07-656616a3fc9e-3807603.jpg"><br><img  srcset="data:image/svg+xml,%3Csvg%20xmlns='http://www.w3.org/2000/svg'%20viewBox='0%200%20300%20300'%3E%3C/svg%3E" data-src="https://api2.mubu.com/v3/document_image/2296be53-0c5e-4072-8618-a28c1f7fb6c5-3807603.jpg" class="lozad post-image"src="https://api2.mubu.com/v3/document_image/2296be53-0c5e-4072-8618-a28c1f7fb6c5-3807603.jpg"></p>
<p>通过构建完成的哈夫曼树，规定左子树编码为 0，右子树编码为 1，则得到新的编码值：</p>
<p>率得知，每个字母的出现概率如下所示：</p>
<table>
<thead>
<tr>
<th>字符</th>
<th>概率</th>
<th>原编码</th>
<th>哈夫曼编码</th>
</tr>
</thead>
<tbody><tr>
<td>A</td>
<td>27%</td>
<td>000</td>
<td>01</td>
</tr>
<tr>
<td>B</td>
<td>8%</td>
<td>001</td>
<td>1001</td>
</tr>
<tr>
<td>C</td>
<td>15%</td>
<td>010</td>
<td>101</td>
</tr>
<tr>
<td>D</td>
<td>15%</td>
<td>011</td>
<td>00</td>
</tr>
<tr>
<td>E</td>
<td>30%</td>
<td>100</td>
<td>11</td>
</tr>
<tr>
<td>F</td>
<td>5%</td>
<td>101</td>
<td>1000</td>
</tr>
</tbody></table>
<p>根据新的编码值，发送如下信息：BADCADFEED （A:2 B:1 C:1 D:3 E:2 F:1）</p>
<p><strong>原编码二进制：</strong>001 000 011 010 000 011 101 100 100 011 （共30个字符）</p>
<p><strong>新编码二进制：</strong>1001 01 00 101 01 00 1001 11 11 00 （共25个字符）</p>
<p>可以清晰地看到在该概率下，哈夫曼编码有效地对数据进行了压缩。</p>
<h2 id="code"><a href="#code" class="headerlink" title="code"></a>code</h2><h3 id="结构"><a href="#结构" class="headerlink" title="结构"></a>结构</h3><pre class="line-numbers language-c++" data-language="c++"><code class="language-c++">&#x2F;&#x2F;&#x2F; 哈夫曼树节点
typedef struct &#123;
    int weight;     &#x2F;&#x2F; 权值
    int flag;       &#x2F;&#x2F; 标志位
    int parent;     &#x2F;&#x2F; 父结点索引
    int lch, rch;   &#x2F;&#x2F; 左右子结点索引
&#125; HaffmanNode;

&#x2F;&#x2F; 编码的长度值
static const int CODE_LEN &#x3D; 3;  

&#x2F;&#x2F;&#x2F; 字符编码结构体
typedef struct  &#123;
    int code[CODE_LEN]; &#x2F;&#x2F; 保存编码的数组
    int length;         &#x2F;&#x2F; 编码的长度
    int weight;         &#x2F;&#x2F; 编码字符的权值
&#125; HaffmanCode;<span aria-hidden="true" class="line-numbers-rows"><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span></span></code></pre>

<p>因为哈夫曼树结点数是确定的，所以采用顺序存储的结构实现二叉树，这样在节点访问上更加便利。</p>
<p>哈夫曼树结点除了二叉树结点必需的三个元素外，还包含了父结点指针、权值与一个标志位，这是为了方便后续向上遍历获取编码的过程。</p>
<p>除了定义树节点，还定义了一个编码结构体用来保存编码的信息，因为哈夫曼编码是不定长的编码。</p>
<h3 id="构建-1"><a href="#构建-1" class="headerlink" title="构建"></a>构建</h3><pre class="line-numbers language-c++" data-language="c++"><code class="language-c++">&#x2F;&#x2F;&#x2F; 根据权重数组，构建哈夫曼树
&#x2F;&#x2F;&#x2F; @param weight 权值数组
&#x2F;&#x2F;&#x2F; @param n 数组个数
&#x2F;&#x2F;&#x2F; @param haffmanNodes 结点数组，顺序存储的哈夫曼树
Status buildHaffmanTree(int weight[], int n, HaffmanNode *haffmanNodes) &#123;
    &#x2F;&#x2F; 1 将权值赋值到结点数组的前面结点中
    for (int i &#x3D; 0; i &lt; 2 * n - 1; i++) &#123;
        if (i &lt; n) &#123;
            haffmanNodes[i].weight &#x3D; weight[i];
        &#125; else &#123;
            haffmanNodes[i].weight &#x3D; 0;
        &#125;
        &#x2F;&#x2F; 初始化其他元素
        haffmanNodes[i].parent &#x3D; -1;
        haffmanNodes[i].lch &#x3D; -1;
        haffmanNodes[i].rch &#x3D; -1;
        haffmanNodes[i].flag &#x3D; 0;
    &#125;
    &#x2F;&#x2F; 2 前面已有 n 个叶子节点，下面构建 n - 1 个树枝结点
    &#x2F;&#x2F; 用来记录当前最小的两个权值
    int min1, min2;
    &#x2F;&#x2F; 用来记录当前最小的两个权值的数组索引
    int index1, index2;
    for (int i &#x3D; 0; i &lt; n - 1; i++) &#123;
        &#x2F;&#x2F; 2.1 初始化权值和索引
        min1 &#x3D; min2 &#x3D; UINT16_MAX;
        index1 &#x3D; index2 &#x3D; 0;
        &#x2F;&#x2F; 2.2 在当前 n 个叶子结点与新建的 i 个树枝结点中，
        &#x2F;&#x2F; 寻找两个最小权值，且未被添加到树中的结点
        for (int j &#x3D; 0; j &lt; n + i; j++) &#123;
            HaffmanNode node &#x3D; haffmanNodes[j];
            if (node.weight &lt; min1 &amp;&amp; node.flag &#x3D;&#x3D; 0) &#123;
                &#x2F;&#x2F; 权值小于 min1 且未被添加到树中
                &#x2F;&#x2F; 将 min1 与 index1 值转移到 min2 和 index2 中
                min2 &#x3D; min1;
                index2 &#x3D; index1;
                &#x2F;&#x2F; min1 与 index1 记录新的最小权值结点
                min1 &#x3D; node.weight;
                index1 &#x3D; j;
            &#125; else if (node.weight &lt; min2 &amp;&amp; node.flag &#x3D;&#x3D; 0) &#123;
                &#x2F;&#x2F; 权值小于 min2 且未被添加到树中
                min2 &#x3D; node.weight;
                index2 &#x3D; j;
            &#125;
        &#125;
        &#x2F;&#x2F; 2.3 已找到两个最小权值的结点，构建新结点
        haffmanNodes[n + i].weight &#x3D; haffmanNodes[index1].weight + haffmanNodes[index2].weight;
        haffmanNodes[n + i].lch &#x3D; index1;
        haffmanNodes[n + i].rch &#x3D; index2;
        &#x2F;&#x2F; 2.4 修改找到的两个结点
        &#x2F;&#x2F; 修改父结点
        haffmanNodes[index1].parent &#x3D; n + i;
        haffmanNodes[index2].parent &#x3D; n + i;
        &#x2F;&#x2F; 修改标志位，表示已被添加到树中
        haffmanNodes[index1].flag &#x3D; 1;
        haffmanNodes[index2].flag &#x3D; 1;
    &#125;
    return SUCCESS;
&#125;<span aria-hidden="true" class="line-numbers-rows"><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span></span></code></pre>

<h3 id="获取编码"><a href="#获取编码" class="headerlink" title="获取编码"></a>获取编码</h3><pre class="line-numbers language-c++" data-language="c++"><code class="language-c++">&#x2F;&#x2F;&#x2F; 根据哈夫曼树获取编码值
&#x2F;&#x2F;&#x2F; @param haffmanNodes 结点数组，顺序存储的哈夫曼树
&#x2F;&#x2F;&#x2F; @param n 数组个数
&#x2F;&#x2F;&#x2F; @param haffmanCodes 编码数组
Status getHaffmanCode(HaffmanNode haffmanNodes[], int n, HaffmanCode haffmanCodes[]) &#123;
    &#x2F;&#x2F; 声明一个编码结构体，用来保存临时数据
    HaffmanCode code;
    &#x2F;&#x2F; 记录向上遍历的索引记录，通过判断左右子树决定编码 0 还是 1
    int child, parent;
    &#x2F;&#x2F; 依次获取 n 个叶子结点的编码值
    for (int i &#x3D; 0; i &lt; n; i++) &#123;
        code.length &#x3D; 0;
        code.weight &#x3D; haffmanNodes[i].weight;
        &#x2F;&#x2F; 由叶子结点向根节点遍历，根节点的 parent 为 -1
        child &#x3D; i;
        parent &#x3D; haffmanNodes[child].parent;
        while (parent !&#x3D; -1) &#123;
            if (child &#x3D;&#x3D; haffmanNodes[parent].lch) &#123;
                &#x2F;&#x2F; 是左子树，添加编码值 0
                code.code[code.length] &#x3D; 0;
            &#125; else &#123;
                &#x2F;&#x2F; 是右子树，添加编码值 1
                code.code[code.length] &#x3D; 1;
            &#125;
            &#x2F;&#x2F; 编码长度加一
            code.length++;
            &#x2F;&#x2F; 继续遍历更上一层
            child &#x3D; parent;
            parent &#x3D; haffmanNodes[child].parent;
        &#125;
        &#x2F;&#x2F; 完成编码的收集，但编码是倒序的，需要进行逆序
        int maxIndex &#x3D; code.length - 1;
        for (int j &#x3D; 0; j &lt;&#x3D; maxIndex; j++) &#123;
            haffmanCodes[i].code[j] &#x3D; code.code[maxIndex - j];
        &#125;
        &#x2F;&#x2F; 保存权值与长度
        haffmanCodes[i].weight &#x3D; code.weight;
        haffmanCodes[i].length &#x3D; code.length;
    &#125;
    return SUCCESS;
&#125;<span aria-hidden="true" class="line-numbers-rows"><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span></span></code></pre>

<h3 id="使用"><a href="#使用" class="headerlink" title="使用"></a>使用</h3><pre class="line-numbers language-c++" data-language="c++"><code class="language-c++">int mainHaffmanTree() &#123;
    &#x2F;&#x2F; 权值数组
    int n &#x3D; 4;
    int weight[] &#x3D; &#123;2, 4, 5, 7&#125;;
    &#x2F;&#x2F; 创建结点数组，顺序存储哈夫曼二叉树，共有 2 * n - 1 个结点
    &#x2F;&#x2F; 其中有 n 个叶子结点表示各个权值，n - 1 个非叶子结点为新构建的权值结点
    HaffmanNode *haffmanNodes &#x3D; malloc(sizeof(HaffmanNode) * 2 * n - 1);
    &#x2F;&#x2F; 创建保存编码值的数组
    HaffmanCode *haffmanCodes &#x3D; malloc(sizeof(HaffmanCode) * n);
    &#x2F;&#x2F; 构建哈弗曼树
    buildHaffmanTree(weight, n, haffmanNodes);
    &#x2F;&#x2F; 根据哈夫曼树获取编码值
    getHaffmanCode(haffmanNodes, n, haffmanCodes);
    &#x2F;&#x2F; 打印编码值
    int wpl &#x3D; 0;
    for (int i &#x3D; 0; i &lt; n; i++) &#123;
        HaffmanCode code &#x3D; haffmanCodes[i];
        printf(&quot;权值：%d 编码：&quot;, code.weight);
        for (int j &#x3D; 0; j &lt; code.length; j++) &#123;
            printf(&quot;%d&quot;, code.code[j]);
        &#125;
        printf(&quot;\n&quot;);
        wpl +&#x3D; code.weight * code.length;
    &#125;
    printf(&quot;哈夫曼树带权路径长度（WPL）为 %d\n&quot;, wpl);
    return 0;
&#125;<span aria-hidden="true" class="line-numbers-rows"><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span></span></code></pre>

<p>打印结果：</p>
<pre class="line-numbers language-c++" data-language="c++"><code class="language-c++">&#x2F;&#x2F;权值：2 编码：110
&#x2F;&#x2F;权值：4 编码：111
&#x2F;&#x2F;权值：5 编码：10
&#x2F;&#x2F;权值：7 编码：0
&#x2F;&#x2F;哈夫曼树带权路径长度（WPL）为 35<span aria-hidden="true" class="line-numbers-rows"><span></span><span></span><span></span><span></span><span></span></span></code></pre>

<p>根据权值数组能轻易地得到哈夫曼树结构，如下图所示。根据树的结构，可以得到对应权值的编码值，与打印结果一致。</p>
<p><img  srcset="data:image/svg+xml,%3Csvg%20xmlns='http://www.w3.org/2000/svg'%20viewBox='0%200%20300%20300'%3E%3C/svg%3E" data-src="https://api2.mubu.com/v3/document_image/3b292fc6-07c6-4c8e-a611-fead1bf671ee-3807603.jpg" class="lozad post-image"src="https://api2.mubu.com/v3/document_image/3b292fc6-07c6-4c8e-a611-fead1bf671ee-3807603.jpg"></p>
<h2 id="参考链接"><a href="#参考链接" class="headerlink" title="参考链接"></a>参考链接</h2><p><a target="_blank" rel="noopener" href="https://juejin.im/post/6844904152242323469">从零开始的数据结构与算法（十）：哈夫曼树</a></p>

  </div>
  <div>
    
  </div>
</article>
<div class="nav">
  
    <div class="nav-item-prev">
      <a 
        href="/2021/06/13/inlineElements/" 
        class="nav-link">
        <i class="iconfont icon-left nav-prev-icon"></i>
        <div>
          <div class="nav-label">上一篇</div>
          
            <div class="nav-title">行内元素、块级元素和行内块级元素 </div>
          
        </div>
      </a>
    </div>
  
  
    <div class="nav-item-next">
      <a 
        href="/2021/06/13/HTTPSWorksWithTheTCPHandshakeMechanism/" 
        class="nav-link">
        <div>
          <div class="nav-label">下一篇</div>
          
            <div class="nav-title">HTTPS的工作原理 </div>
          
        </div>
        <i class="iconfont icon-right nav-next-icon"></i>
      </a>
    </div>
  
</div>

<div 
  class="card card-content toc-card" 
  id="mobiletoc">
  <div class="toc-header">
  <i 
    class="iconfont icon-menu" 
    style="padding-right: 2px;">
  </i>目录
</div>
<ol class="toc"><li class="toc-item toc-level-2"><a class="toc-link" href="#%E5%BC%95%E5%85%A5"><span class="toc-text">引入</span></a></li><li class="toc-item toc-level-2"><a class="toc-link" href="#%E4%BB%8B%E7%BB%8D"><span class="toc-text">介绍</span></a></li><li class="toc-item toc-level-2"><a class="toc-link" href="#%E6%9E%84%E5%BB%BA"><span class="toc-text">构建</span></a></li><li class="toc-item toc-level-2"><a class="toc-link" href="#code"><span class="toc-text">code</span></a><ol class="toc-child"><li class="toc-item toc-level-3"><a class="toc-link" href="#%E7%BB%93%E6%9E%84"><span class="toc-text">结构</span></a></li><li class="toc-item toc-level-3"><a class="toc-link" href="#%E6%9E%84%E5%BB%BA-1"><span class="toc-text">构建</span></a></li><li class="toc-item toc-level-3"><a class="toc-link" href="#%E8%8E%B7%E5%8F%96%E7%BC%96%E7%A0%81"><span class="toc-text">获取编码</span></a></li><li class="toc-item toc-level-3"><a class="toc-link" href="#%E4%BD%BF%E7%94%A8"><span class="toc-text">使用</span></a></li></ol></li><li class="toc-item toc-level-2"><a class="toc-link" href="#%E5%8F%82%E8%80%83%E9%93%BE%E6%8E%A5"><span class="toc-text">参考链接</span></a></li></ol>
</div></main>
            <aside class="left-column">
              
              <div class="card card-author">
                
  <img 
    src="https://api2.mubu.com/v3/photo/654b368e-b847-4122-982c-86d90b3f5275.jpg" 
    class="author-img" 
    alt="author avatar">

<p class="author-name">霜序廿</p>
<p class="author-description">无限进步</p>
<div class="author-message">
  <a 
    class="author-posts-count" 
    href="/archives">
    <span>253</span>
    <span>文章</span>
  </a>
  <a 
    class="author-categories-count" 
    href="/categories">
    <span>6</span>
    <span>分类</span>
  </a>
  <a 
    class="author-tags-count" 
    href="/tags">
    <span>51</span>
    <span>标签</span>
  </a>
</div>

  <div class="author-card-society">
    
      <div class="author-card-society-icon">
        <a target="_blank" rel="noopener" href="https://github.com/shuangxunian">
          <i class="iconfont icon-github society-icon"></i>
        </a>
      </div>
    
      <div class="author-card-society-icon">
        <a target="_blank" rel="noopener" href="https://space.bilibili.com/391117803">
          <i class="iconfont icon-bilibili society-icon"></i>
        </a>
      </div>
    
  </div>

              </div>
               <div class="sticky-tablet">
  
  
    <article class="display-when-two-columns spacer">
      <div class="card card-content toc-card">
        <div class="toc-header">
  <i 
    class="iconfont icon-menu" 
    style="padding-right: 2px;">
  </i>目录
</div>
<ol class="toc"><li class="toc-item toc-level-2"><a class="toc-link" href="#%E5%BC%95%E5%85%A5"><span class="toc-text">引入</span></a></li><li class="toc-item toc-level-2"><a class="toc-link" href="#%E4%BB%8B%E7%BB%8D"><span class="toc-text">介绍</span></a></li><li class="toc-item toc-level-2"><a class="toc-link" href="#%E6%9E%84%E5%BB%BA"><span class="toc-text">构建</span></a></li><li class="toc-item toc-level-2"><a class="toc-link" href="#code"><span class="toc-text">code</span></a><ol class="toc-child"><li class="toc-item toc-level-3"><a class="toc-link" href="#%E7%BB%93%E6%9E%84"><span class="toc-text">结构</span></a></li><li class="toc-item toc-level-3"><a class="toc-link" href="#%E6%9E%84%E5%BB%BA-1"><span class="toc-text">构建</span></a></li><li class="toc-item toc-level-3"><a class="toc-link" href="#%E8%8E%B7%E5%8F%96%E7%BC%96%E7%A0%81"><span class="toc-text">获取编码</span></a></li><li class="toc-item toc-level-3"><a class="toc-link" href="#%E4%BD%BF%E7%94%A8"><span class="toc-text">使用</span></a></li></ol></li><li class="toc-item toc-level-2"><a class="toc-link" href="#%E5%8F%82%E8%80%83%E9%93%BE%E6%8E%A5"><span class="toc-text">参考链接</span></a></li></ol>
      </div>
    </article>
  
  
  <article class="card card-content categories-widget">
    <div class="categories-card">
  <div class="categories-header">
    <i 
      class="iconfont icon-fenlei" 
      style="padding-right: 2px;">
    </i>分类
  </div>
  <div class="categories-list">
    
      <a href="/categories/%E6%8A%80%E6%9C%AF%E6%96%87%E7%AB%A0/">
        <div class="categories-list-item">
          技术文章
          <span class="categories-list-item-badge">218</span>
        </div>
      </a>
    
      <a href="/categories/%E5%85%B6%E4%BB%96/">
        <div class="categories-list-item">
          其他
          <span class="categories-list-item-badge">16</span>
        </div>
      </a>
    
      <a href="/categories/%E6%97%85%E6%B8%B8/">
        <div class="categories-list-item">
          旅游
          <span class="categories-list-item-badge">1</span>
        </div>
      </a>
    
      <a href="/categories/%E7%AE%97%E6%B3%95/">
        <div class="categories-list-item">
          算法
          <span class="categories-list-item-badge">8</span>
        </div>
      </a>
    
      <a href="/categories/%E8%80%83%E8%AF%95/">
        <div class="categories-list-item">
          考试
          <span class="categories-list-item-badge">8</span>
        </div>
      </a>
    
      <a href="/categories/%E9%98%85%E8%AF%BB/">
        <div class="categories-list-item">
          阅读
          <span class="categories-list-item-badge">1</span>
        </div>
      </a>
    
  </div>
</div>
  </article>
  
  <article class="card card-content tags-widget">
    <div class="tags-card">
  <div class="tags-header">
    <i 
      class="iconfont icon-biaoqian" 
      style="padding-right: 2px;">
    </i>热门标签
  </div>
  <div class="tags-list">
    
      <a 
        href="/tags/js/" 
        title="js">
        <div class="tags-list-item">js</div>
      </a>
    
      <a 
        href="/tags/vue/" 
        title="vue">
        <div class="tags-list-item">vue</div>
      </a>
    
      <a 
        href="/tags/%E9%9D%A2%E8%AF%95/" 
        title="面试">
        <div class="tags-list-item">面试</div>
      </a>
    
      <a 
        href="/tags/css/" 
        title="css">
        <div class="tags-list-item">css</div>
      </a>
    
      <a 
        href="/tags/%E7%BD%91%E7%BB%9C/" 
        title="网络">
        <div class="tags-list-item">网络</div>
      </a>
    
      <a 
        href="/tags/%E5%85%B6%E4%BB%96/" 
        title="其他">
        <div class="tags-list-item">其他</div>
      </a>
    
      <a 
        href="/tags/%E7%AE%97%E6%B3%95/" 
        title="算法">
        <div class="tags-list-item">算法</div>
      </a>
    
      <a 
        href="/tags/%E6%B5%8F%E8%A7%88%E5%99%A8/" 
        title="浏览器">
        <div class="tags-list-item">浏览器</div>
      </a>
    
      <a 
        href="/tags/html/" 
        title="html">
        <div class="tags-list-item">html</div>
      </a>
    
      <a 
        href="/tags/%E6%93%8D%E4%BD%9C%E7%B3%BB%E7%BB%9F/" 
        title="操作系统">
        <div class="tags-list-item">操作系统</div>
      </a>
    
      <a 
        href="/tags/%E8%80%83%E8%AF%95/" 
        title="考试">
        <div class="tags-list-item">考试</div>
      </a>
    
      <a 
        href="/tags/%E8%BD%AF%E5%AE%9E%E5%8A%9B/" 
        title="软实力">
        <div class="tags-list-item">软实力</div>
      </a>
    
      <a 
        href="/tags/DOM/" 
        title="DOM">
        <div class="tags-list-item">DOM</div>
      </a>
    
      <a 
        href="/tags/%E8%BD%AE%E5%AD%90/" 
        title="轮子">
        <div class="tags-list-item">轮子</div>
      </a>
    
      <a 
        href="/tags/%E7%BD%91%E7%BB%9C%E5%8E%9F%E7%90%86/" 
        title="网络原理">
        <div class="tags-list-item">网络原理</div>
      </a>
    
      <a 
        href="/tags/debug/" 
        title="debug">
        <div class="tags-list-item">debug</div>
      </a>
    
  </div>
</div>
  </article>
  
  
</div>
            </aside>
            <aside class="right-column">
              <div class="sticky-widescreen">
  
  
    <article class="card card-content toc-card">
      <div class="toc-header">
  <i 
    class="iconfont icon-menu" 
    style="padding-right: 2px;">
  </i>目录
</div>
<ol class="toc"><li class="toc-item toc-level-2"><a class="toc-link" href="#%E5%BC%95%E5%85%A5"><span class="toc-text">引入</span></a></li><li class="toc-item toc-level-2"><a class="toc-link" href="#%E4%BB%8B%E7%BB%8D"><span class="toc-text">介绍</span></a></li><li class="toc-item toc-level-2"><a class="toc-link" href="#%E6%9E%84%E5%BB%BA"><span class="toc-text">构建</span></a></li><li class="toc-item toc-level-2"><a class="toc-link" href="#code"><span class="toc-text">code</span></a><ol class="toc-child"><li class="toc-item toc-level-3"><a class="toc-link" href="#%E7%BB%93%E6%9E%84"><span class="toc-text">结构</span></a></li><li class="toc-item toc-level-3"><a class="toc-link" href="#%E6%9E%84%E5%BB%BA-1"><span class="toc-text">构建</span></a></li><li class="toc-item toc-level-3"><a class="toc-link" href="#%E8%8E%B7%E5%8F%96%E7%BC%96%E7%A0%81"><span class="toc-text">获取编码</span></a></li><li class="toc-item toc-level-3"><a class="toc-link" href="#%E4%BD%BF%E7%94%A8"><span class="toc-text">使用</span></a></li></ol></li><li class="toc-item toc-level-2"><a class="toc-link" href="#%E5%8F%82%E8%80%83%E9%93%BE%E6%8E%A5"><span class="toc-text">参考链接</span></a></li></ol>
    </article>
  
  
  <article class="card card-content">
    <div class="recent-posts-card">
  <div class="recent-posts-header">
    <i 
      class="iconfont icon-wenzhang_huaban" 
      style="padding-right: 2px;">
    </i>最近文章
  </div>
  <div class="recent-posts-list">
    
      <div class="recent-posts-item">
        <div class="recent-posts-item-title">2022-05-01</div>
        <a href="/2022/05/01/typescriptHome/"><div class="recent-posts-item-content">typescript</div></a>
      </div>
    
      <div class="recent-posts-item">
        <div class="recent-posts-item-title">2022-01-15</div>
        <a href="/2022/01/15/javaScriptTheVariousWaysAndAdvantagesAndDisadvantagesOfDeepInheritance/"><div class="recent-posts-item-content">JavaScript深入之继承的多种方式和优缺点</div></a>
      </div>
    
      <div class="recent-posts-item">
        <div class="recent-posts-item-title">2022-01-15</div>
        <a href="/2022/01/15/javaScriptGoFromPrototypeToPrototypeChain/"><div class="recent-posts-item-content">JavaScript深入之从原型到原型链</div></a>
      </div>
    
      <div class="recent-posts-item">
        <div class="recent-posts-item-title">2022-01-15</div>
        <a href="/2022/01/15/javaScriptMemoryLeakTutorial/"><div class="recent-posts-item-content">JavaScript 内存泄漏教程</div></a>
      </div>
    
  </div>
</div>
  </article>
  
  
  
  <article class="card card-content">
    <div class="recent-posts-card">
  <div class="recent-posts-header">
    关注嘉然！顿顿解馋！
  </div>
  <div class="recent-posts-list">
    
      <img 
        src="https://api2.mubu.com/v3/document_image/2697c6ae-10ee-41a3-9099-304bdb252d31-3807603.jpg" 
        class="myadd-img" 
        alt="author avatar">
    
  </div>
</div>
  </article>
</div>
            </aside>
          </div>
        </div>
      </div>
    </div>
     
    <footer class="footer">
  <div class="footer-container">
    <div>
      <div class="footer-dsc">
        <span>
          Copyright ©
          
            2020 -
          
          2022
        </span>
        &nbsp;
        <a 
          href="/" 
          class="footer-link">
          霜序廿的个人网站
        </a>
      </div>
    </div>

    
      <div class="footer-dsc">
        
          Powered by
          <a 
            href="https://hexo.io/" 
            class="footer-link" 
            target="_blank" 
            rel="nofollow noopener noreferrer">
            &nbsp;Hexo
          </a>
        
        
          <span>&nbsp;|&nbsp;</span>
        
        
          Theme -
          <a 
            href="https://github.com/theme-kaze" 
            class="footer-link" 
            target="_blank"
            rel="nofollow noopener noreferrer">
            &nbsp;Kaze
          </a>
        
      </div>
    
    
    
    
</footer> 
    
  <a 
    role="button" 
    id="scrollbutton" 
    class="basebutton" 
    aria-label="回到顶部">
    <i class="iconfont icon-arrowleft button-icon"></i>
  </a>

<a 
  role="button" 
  id="menubutton" 
  class="basebutton">
  <i class="iconfont icon-menu button-icon"></i>
</a>
<a 
  role="button" 
  id="popbutton" 
  class="basebutton" 
  aria-label="控制中心">
  <i class="iconfont icon-expand button-icon"></i>
</a>
<a 
  role="button" 
  id="darkbutton" 
  class="basebutton darkwidget" 
  aria-label="夜色模式">
  <i class="iconfont icon-weather button-icon"></i>
</a>
<a 
  role="button" 
  id="searchbutton" 
  class="basebutton searchwidget" 
  aria-label="搜索">
  <i class="iconfont icon-search button-icon"></i>
</a> 
     
     
     
      <script>
  var addImgLayout = function () {
    var img = document.querySelectorAll('.post-content img')
    var i
    for (i = 0; i < img.length; i++) {
      var wrapper = document.createElement('a')
      wrapper.setAttribute('href', img[i].getAttribute('data-src'))
      wrapper.setAttribute('aria-label', 'illustration')
      wrapper.style.cssText =
        'width: 100%; display: flex; justify-content: center;'
      if (img[i].alt) wrapper.dataset.caption = img[i].alt
      wrapper.dataset.nolink = true
      img[i].before(wrapper)
      wrapper.append(img[i])
      var divWrap = document.createElement('div')
      divWrap.classList.add('gallery')
      wrapper.before(divWrap)
      divWrap.append(wrapper)
    }
    baguetteBox.run('.gallery')
  }
</script>
<script>
  loadScript(
    "/js/lib/lightbox/baguetteBox.min.js",
    addImgLayout
  )
</script>
 
     
     
    <script src="/js/main.js"></script> 
     
    
      <script>
        var addLazyload = function () {
          var observer = lozad('.lozad', {
            load: function (el) {
              el.srcset = el.getAttribute('data-src')
            },
            loaded: function (el) {
              el.classList.add('loaded')
            },
          })
          observer.observe()
        }
      </script>
      <script>
        loadScript('/js/lib/lozad.min.js', addLazyload)
      </script>
     
    
    
  </body>
</html>
